package io.github.hadyang.leetcode.offer;

import java.util.LinkedList;

import io.github.hadyang.leetcode.TreeNode;

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 *
 * @author haoyang.shi
 */
public class HasSubtree {

  public boolean HasSubtree(TreeNode root1, TreeNode root2) {
    if (root2 == null) {
      return false;
    }

    LinkedList<TreeNode> pipeline = new LinkedList<>();
    pipeline.addLast(root1);

    while (!pipeline.isEmpty()) {
      TreeNode node = pipeline.pop();
      if (node == null) {
        continue;
      }

      pipeline.addLast(node.left);
      pipeline.addLast(node.right);

      if (node.val == root2.val && isSub(node, root2)) {
        return true;
      }
    }

    return false;
  }

  private boolean isSub(TreeNode root1, TreeNode root2) {
    if (root1 == null && root2 == null) {
      return true;
    }

    if (root1 == null) {
      return false;
    }

    if (root2 == null) {
      return true;
    }

    if (root1.val == root2.val) {
      return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
    } else {
      return false;
    }
  }
}
